;;; What is the first term in the Fibonacci sequence to contain 1000 digits?
;;;
;;; TODO using lucas formula 
;;;
;;;
(defvar *GOLDEN_RATE* (/ (1+ (sqrt 5)) 2))

(defun fib-2 (seq)
  (defun fib-inner (k a b)
	(if (= k 1)
	    a
		(fib-inner (1- k) (+ a b) a)))
  (if (< seq 2)
	  seq
	  (fib-inner seq 1 0)))

;;; TODO floating point overflow when testing (fib-3 4782)
(defun fib-3 (n)
  (truncate (- (/ (expt *GOLDEN_RATE* n) (sqrt 5)) 0.5)))

(defun fib (n)
  (loop for i below n
      and a = 0 then b
      and b = 1 then (+ b a)
      finally (return  a))
)  
;;; TODO 2390
;;; store (fib i) to tmp value
(defun p25 (length)
  (do ((i 0 (1+ i)))
	  ((>= (length (write-to-string (fib i))) length) i)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;(format t "~a~%" *GOLDEN_RATE*)
(format t "~a~%" (time (fib 4782)))
;(format t "~a~%" (time (fib-3 4782)))
;(format t "~a~%" (length (write-to-string (fib 4782))))
(format t "~a~%" (time (p25 1000)))



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
"""
A number contains 1000 digits is the same as that it's greater than 10**999.

The nth Fibonacci number is [phi**n / sqrt(5)], the brackets denote 'nearest integer'.

So we need phi**n/sqrt(5) > 10**999

n * log(phi) - log(5)/2 > 999 * log(10)
n * log(phi) > 999 * log(10) + log(5)/2
n > (999 * log(10) + log(5) / 2) / log(phi)
n > 4781.9583

thus (result n) = 4782
"""
